Existing router architectures and routing protocols lack certain desirable features. For the purposes of this discussion, router architectures and routing protocols include bridging spanning tree protocols (STPs) as well as routing protocols such as Open Shortest Path First (OSPF) and BGP-4 (Border Gateway Protocol version 4).
OSPF is a link-state routing protocol. It is designed to be run internally of a single Autonomous System (AS). Each OSPF router maintains an identical database describing the AS's topology. From this database, a routing table is calculated by constructing a shortest-path tree. OSPF recalculates routes quickly in response to topological changes, utilizing a minimum of routing protocol traffic. OSPF provides support for equal-cost multipath. An area routing capability is also provided, enabling an additional level of routing protection and a reduction in routing protocol traffic. In addition, all OSPF routing protocol exchanges are authenticated.
BGP-4 is an inter-Autonomous System routing protocol. The primary function of a BGP-4 enabled system is to exchange network reachability information with other BGP-4 systems. The network reachability information includes information about a list of ASs that reachability information traverses. The reliability information is sufficient to construct a graph of AS connectivity from which routing loops may be pruned and certain policy decisions at the AS level may be enforced. BGP-4 also provides a new set of mechanisms for supporting classless inter-domain routing. These mechanisms include support for advertising an Internet Protocol (IP) prefix and eliminates the concept of network class within BGP. BGP-4 also introduces mechanisms that allow aggregation of routes, including aggregation of AS paths. To characterize the set of policy decisions that can be enforced using BGP, one must focus on the rule that a BGP-4 speaker advertises to its peers (other BGP-4 speakers with which it communicates) in neighboring ASs only those routes that it uses itself. This rule reflects the “hop-by-hop” routing paradigm generally used throughout the current Internet.
It should be noted that some policies cannot be enforced by the “hop-by-hop” routing paradigm, and thus require methods such as source routing. For example, BGP-4 does not enable one AS to send traffic to a neighboring AS with the intention that the traffic take a different route from that taken by traffic originating in the neighboring AS. On the other hand, BGP-4 can support any policy conforming to the “hop-by-hop” routing paradigm. Since the current Internet only uses the “hop-by-hop” routing paradigm, and since BGP-4 can support any policy that conforms to that paradigm, BGP-4 is highly applicable as an inter-AS routing protocol for the current Internet.
L3 (layer 3 of the open system interconnection model) routing and bridging protocols were not designed to easily allow dual or synchronous standby architectures within routing switches to provide high-availability. Typically, high-availability for packet forwarding equipment is achieved through physical duplication of switches. Physical duplication has a high cost due to increased footprint, ongoing management, and cabling costs. It is therefore advantageous to be able to provide a highly reliable and available solution to minimize these costs. Furthermore, physical duplication generally fails to address the most common point of failure in modern packet forwarding equipment, namely software crashes due to errors in program code. Due to the increasing complexity and feature support in modern packet forwarding software, it is difficult to provide software loads that are completely error free. Current packet forwarding systems, however, fail to adequately address detection and failover for software faults.
High-availability for packet forwarding requires a number of features, including: 1) the ability to perform hitless software upgrades; 2) the ability to provide hitless control path failover due to either software or hardware faults; 3) the ability to provide hitless line card failover; 4) the ability to provide hitless path failover, and 5) other features, including synchronization of Routing/Bridging states using database synchronization, which is difficult to provide due to the large amount of state information required to maintain synchronization. Currently, packet forwarding technology does not support hitless software upgrade or failover, much less the other desirable features listed above.
As is known in the art, there exist a number of methods for providing fault protection for packet network paths. Packet network routing has developed to support improved reliability for data delivery, providing for special, expedient, handling of identifiable packets using such protocols as multi-path label switching (MPLS). With these developments have also come tools for providing fault protection for these delivery techniques. A wide variety of fault protection schemes are available using label switched paths (LSPs) established using label distribution protocol (LDP), or resource reservation protocol (RSVP), for example. A common protection scheme requires setting up primary and backup LSPs by reserving bandwidth for each label switched path on the same or separate links. To provide continuation of MPLS network connections during a failover, the backup LSPs are reserved for the network connection. MPLS tags, in particular traffic-engineered outer tags, may be used for identifying packets for a separate systematic routing procedure. While it is known to protect against equipment failures using a backup LSP to support a network connection, this is an expensive option that ties up considerable network resources.
It therefore remains highly desirable to provide a means of achieving a high level of packet forwarding availability at a reasonable cost and complexity.